#include <vector>
#include <map>
#include <functional>
#include <stack>
#include <string>
#include <ctype.h>
#include <iostream>
using namespace std;

// 这个题是完成基本计算器

//但是，我打算写一个类，即计算机器，完成简单计算器的过程
//然后把这个题中需要实现的函数给加在里面



class Calculator{
public:

    Calculator(){
        _OprLevel = {
            {"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}
        };
    }

    ~Calculator(){}

private:
    // 接收一个后缀的表达式，然后进行计算！
    int evalRPN(vector<string>& tokens) {

        // 这个是没有任何空格的
        map<string, std::function<int(int, int)>> matchOpr = {
            {"+", [](int x, int y){return x + y;}},
            {"-", [](int x, int y){return x - y;}},
            {"*", [](int x, int y){return x * y;}},
            {"/", [](int x, int y){return x / y;}}
        };

        stack<int> st;

        for(auto str : tokens){
            if(matchOpr.count(str)){
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();

                st.push(matchOpr[str](left, right));
            }
            else st.push(stoi(str));
        }

        return st.top();
    }

    // 得有一个中缀 -> 转后缀的方法(假设这个中缀表达式是不带任何的括号的)
    void ToRPN(string& str, int& i, vector<string>& tokens){
        // 方法：
        //定义一个栈
        stack<char> st;

        //遍历str，如果是操作数，就直接输出到 vector<string>& tokens
        //如果是操作符 -> {
            //1.如果栈为空，那么就直接入栈
            //2.如果栈不为空，当前遍历操作符的优先级 > 栈顶的操作符，直接入栈
            //3.当前遍历操作符的优先级 <= 栈顶的操作符，栈顶的操作符可以输出
            //然后当前操作符继续走上述逻辑！(其实就是不要让i坐标移动罢了)
        //}
        //但是，如果碰到了(),这个时候就说明碰到了一个子表达式
        //子表达式递归处理！处理完后再来输出！
        
        //因为坐标i是引用给的，所以是一直往后移动的！tokens是外界传进来的，输出到这里就可以了！

        while(i < str.size()){
            // 操作数
            if(isdigit(str[i])){
                // 这里是用string来表示数字，很有可能数字是多位数
                string num;
                int j = i;
                while(j < str.size()){
                    if(isdigit(str[j])){
                        num += str[j];
                        ++j;
                    }
                    else break;
                }
                tokens.push_back(num);
                i = j;
            }
            //左括号
            else if(str[i] == '('){
                //递归处理！
                ++i;//越过这个'('
                ToRPN(str, i, tokens);
            }
            //右括号
            else if(str[i] == ')'){
                // 说明子表达式处理完成
                // 输出所有栈中的运算符
                while(!st.empty()){
                    tokens.push_back(string(1, st.top()));
                    st.pop();
                }
                ++i;//越过这个')'
                return;
            }

            //运算符
            else{
                //首先得有比较优先级的方法
                string opr_cur = string(1, str[i]);
                string opr_top;
                if(!st.empty()) opr_top = string(1, st.top());
                if(st.empty() || _OprLevel[opr_cur] > _OprLevel[opr_top]){
                    st.push(str[i]);
                    ++i;
                }
                else {
                    //输出当前栈顶操作符
                    tokens.push_back(opr_top);
                    st.pop();
                }
            }
        }
        

        // 整个表达式完成！
        while(!st.empty()){
            tokens.push_back(string(1, st.top()));
            st.pop();
        }
    }

    string StandFormat(string s){
        string news;
        //1.先处理空格
        for(auto& ch : s){
            if(ch != ' ')
                news += ch;
        }

        cout << news << endl;

        //2.再处理负数
        //负数的情况可能有若干种：
        //如果是负数，那么减号被翻译为负号！

        //那么其前面： 
        //1. 前面是')'  -> 减号   (3 - 5) - 5
        //2. 前面是'('  -> 负号   (-3 - 5)
        //3. 前面是数字 ->  减号   3 - 5
        //4. 如果有这种情况： 3 / -5 那么还是负号
        //5. 还有一种可能，因为要判断负号前面，如果前面为空，就很麻烦：
        // -3 - 5，前面为空，也是负号！


        s = news;
        news.clear();

        for(int i = 0; i < s.size(); ++i){
            // 1.判定为负号
            if(s[i] == '-' && ((i == 0) || !isdigit(s[i - 1])  && s[i - 1] != ')')){
                news += "0-";
            }
            //2.判定为减号 || 其他内容 -> 正常写
            else news += s[i]; 
        }

        return news;
    }


    


public:
    // 给用户进行计算！
    int calculate(string s) {
        //问题：
        //用户给进来的string，可能是有很多的空格的！ -> 先消去空格
        //用户给的字符string中，如果有负数怎么办？ -> 把负数-x 变成 0-x

        //problem1 -> 先消去空格(把消去空格后的字符串放在新串)
        _eval = StandFormat(s);
        cout << _eval << endl;


        // 1. 先把中缀转为后缀
        int i = 0;
        ToRPN(_eval, i, _tokens);
        for(auto& str : _tokens){
            cout << str;
        }
        cout << endl;

        // 2. 把对应的后缀表达式计算求值
        return evalRPN(_tokens);
    }

private:
    string _eval;
    vector<string> _tokens;
    map<string, int> _OprLevel;
};






int main(){
    Calculator cal;
    cout << cal.calculate("(1+(4+5+2)-3)+(6+8)") << endl; 




    return 0;
}